Understanding HIV transmission dynamics is critical to estimating the potential population-wide impact of HIV prevention and treatment interventions. We developed an individual-based simulation model of the heterosexual HIV epidemic in South Africa and linked it to the previously published Cost-Effectiveness of Preventing AIDS Complications (CEPAC) International Model, which simulates the natural history and treatment of HIV. In this new model, the CEPAC Dynamic Model (CDM), the probability of HIV transmission per sexual encounter between short-term, long-term and commercial sex worker partners depends upon the HIV RNA and disease stage of the infected partner, condom use, and the circumcision status of the uninfected male partner. We included behavioral, demographic and biological values in the CDM and calibrated to HIV prevalence in South Africa pre-antiretroviral therapy. Using a multi-step fitting procedure based on Bayesian melding methodology, we performed 264,225 simulations of the HIV epidemic in South Africa and identified 3,750 parameter sets that created an epidemic and had behavioral characteristics representative of a South African population pre-ART. Of these parameter sets, 564 contributed 90% of the likelihood weight to the fit, and closely reproduced the UNAIDS HIV prevalence curve in South Africa from 1990–2002. The calibration was sensitive to changes in the rate of formation of short-duration partnerships and to the partnership acquisition rate among high-risk individuals, both of which impacted concurrency. Runs that closely fit to historical HIV prevalence reflect diverse ranges for individual parameter values and predict a wide range of possible steady-state prevalence in the absence of interventions, illustrating the value of the calibration procedure and utility of the model for evaluating interventions. This model, which includes detailed behavioral patterns and HIV natural history, closely fits HIV prevalence estimates.